struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution
{
public:
    // 思路： 使用一个新的链表，依次将两个链表的节点值相加，
    //        并考虑进位，直到两个链表都为空，如果最后还有进位，则将进位作为新的节点添加到结果链表的末尾。
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2)
    {
        ListNode *dummy = new ListNode(0); // 哨兵
        ListNode *tail = dummy;
        int n = 0;
        while (l1 && l2)
        {
            int sum = l1->val + l2->val + n;
            n = 0;
            if (sum > 9)
            {
                n = sum / 10;
                sum %= 10;
            }
            tail->next = new ListNode(sum);
            l1 = l1->next;
            l2 = l2->next;
            tail = tail->next;
        }
        while (l1)
        {
            int sum = l1->val + n;
            n = 0;
            if (sum > 9)
            {
                n = sum / 10;
                sum %= 10;
            }
            tail->next = new ListNode(sum);
            l1 = l1->next;
            tail = tail->next;
        }
        while (l2)
        {
            int sum = l2->val + n;
            n = 0;
            if (sum > 9)
            {
                n = sum / 10;
                sum %= 10;
            }
            tail->next = new ListNode(sum);
            l2 = l2->next;
            tail = tail->next;
        }
        if (n)
        {
            tail->next = new ListNode(n);
        }
        return dummy->next;
    }
};